#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define MAX_V 5     // 最大顶点数
#define INF INT_MAX // 表示无穷大

// 邻接表结点结构（带权值）
typedef struct AdjListNode
{
    int vertex;               // 邻接顶点索引
    int weight;               // 边权值
    struct AdjListNode *next; // 指向下一个邻接结点
} AdjListNode;

// 顶点结构
typedef struct
{
    char name[3];      // 顶点名称
    AdjListNode *head; // 邻接表头指针
} Vertex;

// 图结构
typedef struct
{
    Vertex vertices[MAX_V]; // 顶点数组
    int vCount;             // 当前顶点数
} Graph;

// 1. 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;
    return g;
}

// 2. 添加顶点
void addVertex(Graph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    strcpy(g->vertices[g->vCount].name, name);
    g->vertices[g->vCount].head = NULL;
    g->vCount++;
}

// 3. 添加边（有向图）
void addEdge(Graph *g, int v1, int v2, int weight)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    // 为v1添加v2邻接结点
    AdjListNode *newNode = (AdjListNode *)malloc(sizeof(AdjListNode));
    newNode->vertex = v2;
    newNode->weight = weight;
    newNode->next = g->vertices[v1].head;
    g->vertices[v1].head = newNode;
}

// 4. 找到未处理顶点中距离最小的顶点
int minDistance(int dist[], int final[], int vCount)
{
    int min = INF, min_index = -1;
    for (int v = 0; v < vCount; v++)
    {
        if (!final[v] && dist[v] <= min)
        {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// 5. Dijkstra算法寻找最短路径
void Dijkstra(Graph *g, int startIndex)
{
    if (startIndex < 0 || startIndex >= g->vCount)
    {
        printf("Error: Invalid start index\n");
        return;
    }
    int dist[MAX_V];  // 存储最短距离
    int final[MAX_V]; // 标记是否已找到最短路径
    int path[MAX_V];  // 存储前驱结点
    // 初始化
    for (int i = 0; i < g->vCount; i++)
    {
        dist[i] = INF;
        final[i] = 0;
        path[i] = -1;
    }
    // 起始顶点距离设为0
    dist[startIndex] = 0;
    // 寻找最短路径
    for (int count = 0; count < g->vCount - 1; count++)
    {
        // 选择未处理顶点中距离最小的顶点
        int u = minDistance(dist, final, g->vCount);
        if (u == -1)
            break; // 所有可达顶点已处理

        final[u] = 1; // 标记为已处理
        // 更新u的邻接顶点的距离
        AdjListNode *node = g->vertices[u].head;
        while (node != NULL)
        {
            int v = node->vertex;
            if (!final[v] && dist[u] != INF &&
                dist[u] + node->weight < dist[v])
            {
                dist[v] = dist[u] + node->weight;
                path[v] = u;
            }
            node = node->next;
        }
    }
    // 打印结果
    printf("node\tfinal\tdist\tpath\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s\t", g->vertices[i].name);
        printf("%d\t", final[i]);
        if (dist[i] == INF)
            printf("INF\t");
        else
            printf("%d\t", dist[i]);

        if (path[i] == -1)
            printf("NULL\n");
        else
            printf("%s\n", g->vertices[path[i]].name);
    }
}

// 6. 销毁图
void destroyGraph(Graph *g)
{
    if (!g)
        return;
    // 释放邻接表
    for (int i = 0; i < g->vCount; i++)
    {
        AdjListNode *node = g->vertices[i].head;
        while (node)
        {
            AdjListNode *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点
    addVertex(g, "V0");
    addVertex(g, "V1");
    addVertex(g, "V2");
    addVertex(g, "V3");
    addVertex(g, "V4");

    // 添加边（构建指定图）
    addEdge(g, 0, 4, 5);  // V0->5->V4
    addEdge(g, 0, 1, 10); // V0->10->V1
    addEdge(g, 4, 3, 2);  // V4->2->V3
    addEdge(g, 4, 1, 3);  // V4->3->V1
    addEdge(g, 4, 2, 9);  // V4->9->V2
    addEdge(g, 1, 4, 2);  // V1->2->V4
    addEdge(g, 1, 2, 1);  // V1->1->V2
    addEdge(g, 2, 3, 4);  // V2->4->V3
    addEdge(g, 3, 2, 6);  // V3->6->V2
    addEdge(g, 3, 0, 7);  // V3->7->V0

    // 从V0开始寻找最短路径
    Dijkstra(g, 0);

    // 销毁图
    destroyGraph(g);
    return 0;
}